package array;

/**
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，
 * 要求也按 非递减顺序 排序。
 */
public class leetCode977_sortedSquares {
    public static void main(String[] args) {
        int[] nums = {-5,-3,-2,-1};
        leetCode977_sortedSquares a = new leetCode977_sortedSquares();
        int[] ints = a.sortedSquares2(nums);
        System.out.println(1);
    }

    public int[] sortedSquares2(int[] nums) {
        int[] result = new int[nums.length];
        if(nums.length == 0) return nums;
        int left = 0;
        int right = nums.length - 1;
        int flag = nums.length - 1;
        while (left <= right && flag >= 0){
            int i = nums[left] * nums[left];
            int j = nums[right] * nums[right];
            if(i > j){
                result[flag] = i;
                left++;
            }else{
                result[flag] = j;
                right--;
            }
            flag--;
        }
        return result;
    }

    public int[] sortedSquares(int[] nums) {
        if(nums.length == 0) return nums;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums,0,nums.length - 1);
        System.out.println(1);
        return nums;
    }

    public void sort(int[] nums,int start,int end){

        if(start >= end){
            return;
        }
        int mid = getMid(nums, start, end);

        sort(nums,start,mid - 1);
        sort(nums,mid+1,end);


    }

    public int getMid(int[] nums, int start, int end){
        int point = nums[start];
        int left = start;
        int right = end;

        while (left < right){
            while (left < right && nums[right] > point){
                right--;
            }
            while (left < right && nums[left] <= point){
                left++;
            }
            if(left < right){
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }
        nums[start] = nums[left];
        nums[left] = point;
        return left;


    }

}
